package heap;

import java.util.*;

public class LeastK {
    /*
    给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
     */
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        for(int i = 0;i<nums.length;i++){
            maxHeap.add(nums[i]);
        }
        Integer maxK = 0;
        while(!maxHeap.isEmpty() && k>0){
            k--;
            maxK = maxHeap.poll();
        }
        Arrays.sort(nums);
        return maxK;
    }
    public int partition(int [] nums , int first , int end){
        int temp;
        int i = first;
        int j = end;
        while(i<j){
            while(i<j && nums[i] <= nums[j]){
                j--;
            }
            if(i < j){
                temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
            }
            while(i < j && nums[i] <= nums[j]){
                i++;
            }
            if(i < j){
                temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                j--;
            }
        }
        return i;
    }
    public void sortQuick(int nums[],int first,int end){
        if(first < end){
            int pivot = partition(nums,first,end);
            sortQuick(nums,pivot + 1,end);
            sortQuick(nums,first,pivot - 1);
        }
    }

}
class MostK{
    /*
    给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
     */
    public int[] topKFrequent(int[] nums, int k) {
        int res[] = new int[k];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        PriorityQueue<Map.Entry<Integer, Integer>> min =
                new PriorityQueue<>((e1, e2) -> e1.getValue().compareTo(e2.getValue()));
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (min.size() < k) {
                min.offer(entry);
            } else if (entry.getValue() > min.peek().getValue()) {
                min.poll();
                min.offer(entry);
            }
        }
        int i = 0;
        while (!min.isEmpty() && i < k) {
            res[i] = min.poll().getKey();
            i++;
        }
        return res;
    }
}
/*
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:
MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
示例 1：
输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]
解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0
 */
class MedianFinder {
    private PriorityQueue<Integer> left ;
    private PriorityQueue<Integer> right;
    public MedianFinder() {
        left = new PriorityQueue<>((a,b)->b-a);
        right = new PriorityQueue<>();
    }

    public void addNum(int num) {
       if(left.size() == right.size()){
           right.offer(num);
           left.offer(right.poll());
       }else {
           left.offer(num);
           right.offer(left.poll());
       }
    }

    public double findMedian() {
       if(left.size() == right.size()){
           return (double)(right.peek() + left.peek()) / 2;
       }else{
           return left.peek();
       }
    }
}

class Main{
    public static void main(String[] args) {
        int nums[] = {1,1,1,2,2,3};
        MostK mostK = new MostK();
        int[] ints = mostK.topKFrequent(nums, 2);
    }
}
